#include <stdio.h>
#include <stdlib.h>
//#include <windows.h>

typedef struct node
{
    int number;
    struct node *next;
};

void add(struct node *node, struct node *head, int order);   // 把节点按顺序加入链表。把 node 加入 head 为头节点的链表。order 代表排序顺序，1 代表从小到大，-1 代表从大到小。
void freememory(struct node *rubbish);                      // 释放以 rubbish 为头节点的链表
void merge(struct node *head1, struct node *head2);        // 融合分别以 head1 和 head2 为头节点的链表，把 head2 的子节点添加到 head1 下面，并销毁 head2 头节点。
void printchain(struct node *head);                       // 输入一个链表的头节点 head，输出它的所有节点的值
struct node *reverse(struct node *head);                 // 输入一个链表的头节点，返回翻转链表的头节点指针，并释放原链表的内存。

int main()
{
    int round;
    struct node *ehead, *onode, *pend;
    struct node *ohead, *enode, *nend;
    int input;
    ehead = (struct node *)malloc(sizeof(struct node));
    ohead = (struct node *)malloc(sizeof(struct node));
    ehead->next = NULL;
    ohead->next = NULL;
    pend = ehead;
    nend = ohead;
    //printf("Please enter %d numbers\n", INPUTS);
    round = 0;
    while (scanf("%d", &input) != EOF)
    {
        if (input < 0)
        {
            onode = (struct node *)malloc(sizeof(struct node));
            onode->number = input;
            add(onode, ohead, 1);
        }
        else
        {
            enode = (struct node *)malloc(sizeof(struct node));
            enode->number = input;
            add(enode, ehead, 1);
        }
        round++;
    }
    //printf("\nEven numbers: \n");
    printchain(ehead);
    //printf("\nOdd numbers: \n");
    printchain(ohead);
    //printf("\nReversed even numbers:\n");
    ehead = reverse(ehead);
    printchain(ehead);
    //printf("\nReversed even numbers:\n");
    ohead = reverse(ohead);
    printchain(ohead);
    //printf("\nFree even numbers chain memory:\n");
    freememory(ehead);
    //printf("\nFree odd numbers chain memory:\n");
    freememory(ohead);
    //system("pause");
    return 0;
}

void add(struct node *node, struct node *head, int order)
{

    struct node *tmpnode;
    tmpnode = head;
    while (1)
    {
        node->next = tmpnode->next;
        if(order == 1)
        {
        if (tmpnode->next == NULL || node->number <= tmpnode->next->number)
        {
            tmpnode->next = node;
            break;
        }
        }
        else
        {
            if (tmpnode->next == NULL || node->number >= tmpnode->next->number)
            {
                tmpnode->next = node;
                break;
            }
        }
        tmpnode = tmpnode->next;
    }
}

struct node * reverse(struct node *head)
{
    struct node *oldnode;
    struct node *newnode;
    struct node *newhead;
    oldnode = head;
    newhead = (struct node *)malloc(sizeof(struct node));
    newhead->next = NULL;
    while(oldnode->next != NULL)
    {
        oldnode = oldnode->next;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->number = oldnode->number;
        add(newnode, newhead, -1);
    }
    freememory(head);
    return newhead;
}

void printchain(struct node *head)
{
    struct node *tmpnode;
    for (tmpnode = head; tmpnode->next != NULL; tmpnode = tmpnode->next)
    {
        printf("%d", tmpnode->next->number);
        if (tmpnode->next->next != NULL)
        {
            printf("->");
        }
    }
    printf("\n");
}

void freememory(struct node *rubbish)
{
    struct node *pointer;
    while (rubbish != NULL)
    {
        pointer = rubbish;
        rubbish = rubbish->next;
        //printf("Free memory: %p\n", pointer);
        free(pointer);
    }
}